package 两两交换链表中的节点;

class Solution {

    //给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。


    public ListNode swapPairs(ListNode head) {

        // q指针指向当前待处理的相邻的起始节点，例如 1 2 3 4.... ，那么此时p指向1号节点
        ListNode p=head;
        // 如果链表节点数小于2,则直接返回
        if ( head == null || head.next == null ){
            return head;
        }
        // q指针指向下一对相邻的起始节点，例如 1 2 3 4.... ，那么此时q指向3号节点
        ListNode q = head.next.next;
        // 如果通过了if判断，代表head头节点一定变为了原链表的第二个节点
        head = p.next;

        // 逆转相邻链表
        while ( true ){
            // 例1：如果是 1 2 3 4 四个节点，改变指针为 2->1
            p.next.next = p;
            // 没有下一对相邻的节点，且q已经是末尾了
            if ( q == null ){
                p.next = null;
                return head;
            }
            if( q.next == null ){
                // 没有下一对相邻的节点，但还有一个单节点未处理
                p.next = q;
                return head;
            }else {
                // 还有至少一对节点未处理
                p.next = q.next;
            }
            p = q;
            q = q.next.next;
        }
    }
}